//
// Created by win10 on 24-12-25.
//


#include <stdio.h>

void printArray(int arr[],int size) {
    for(int i=0;i<size-1;i++) {
        printf("%d ",arr[i]);
    }
    printf("%d\n",arr[size-1]);
}

//插入排序
//1.待排序的值 进行逐个的遍历 插入到正确的位序当中
//2.逐个的值和已排序的序列 从后往前依次比较
void insertionSort(int arr[],int n) { //arr待排序的数组 n数组的尺寸
    //1.待排序的值 进行逐个的遍历 插入到正确的位序当中
    for(int i=1;i<n;i++) {
        //i=1 默认下标为零的值 为初始的有序序列
        int key=arr[i];//key作为临时变量 进行逐个比较
        int j=i-1;//需要一个开始比较的下标位序


        //2.逐个的值和已排序的序列 从后往前依次比较
        while(j>=0 && arr[j]>key) {//因为是升序所以是>
            arr[j+1]=arr[j];//因为比排序的值要大 所以后移一位
            j--;
        }

        //3.值插入到正确的位置
        arr[j+1]=key;
        printArray(arr,n);
    }
}

int main() {
    int arr[]={1,13,24,11,26,23,10};
    int n=sizeof(arr)/sizeof(arr[0]);  //计算尺寸
    printArray(arr,n);

    insertionSort(arr,n);
}
